# Definition for double-linked list.
class ListNode:
    def __init__(self):
        self.next = None
        self.pre = None
        self.keys = set()

    def addKey(self, key):
        self.keys.add(key)

    def removeKey(self, key):
        self.keys.remove(key)

    def isEmpty(self):
        return len(self.keys) == 0

    def getKey(self):
        if self.isEmpty():
            return ""
        key = self.keys.pop()
        self.keys.add(key)

        return key


class AllOne:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.table = {}
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.pre = self.head
        self.ctable = {}
        self.ntable = {}

    def __removeNode(self, node):
        preNode = node.pre
        nextNode = node.next
        preNode.next = nextNode
        nextNode.pre = preNode

    def __insertBefore(self, node, before):
        preNode = node.pre
        preNode.next = before
        before.pre = preNode
        before.next = node
        node.pre = before

    def __insertAfter(self, node, after):
        nextNode = node.next
        nextNode.pre = after
        after.next = nextNode
        node.next = after
        after.pre = node

    def inc(self, key: str) -> None:
        """
        Inserts a new key <Key> with value 1. Or increments an existing key by 1.
        """
        if key not in self.table:
            self.table[key] = 1
            val = self.table[key]
            if val not in self.ctable:
                self.ctable[val] = 0
            self.ctable[val] += 1
            if val not in self.ntable:
                self.ntable[val] = ListNode()
                self.__insertBefore(self.tail, self.ntable[val])
            self.ntable[val].addKey(key)
        else:
            oval = self.table[key]
            onode = self.ntable[oval]
            self.table[key] += 1
            nval = self.table[key]
            self.ctable[oval] -= 1
            if nval not in self.ctable:
                self.ctable[nval] = 0
            self.ctable[nval] += 1
            if self.ctable[oval] == 0:
                del self.ctable[oval]
                del self.ntable[oval]
                if nval in self.ntable:
                    self.ntable[nval].addKey(key)
                else:
                    self.ntable[nval] = ListNode()
                    self.ntable[nval].addKey(key)
                    self.__insertBefore(onode, self.ntable[nval])
                self.__removeNode(onode)
            else:
                onode.removeKey(key)
                if nval in self.ntable:
                    self.ntable[nval].addKey(key)
                else:
                    self.ntable[nval] = ListNode()
                    self.ntable[nval].addKey(key)
                    self.__insertBefore(onode, self.ntable[nval])

    def dec(self, key: str) -> None:
        """
        Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
        """
        if key not in self.table:
            return
        oval = self.table[key]
        onode = self.ntable[oval]
        self.table[key] -= 1
        nval = self.table[key]
        if nval == 0:
            del self.table[key]
            self.ctable[oval] -= 1
            self.ntable[oval].removeKey(key)
            if self.ctable[oval] == 0:
                del self.ctable[oval]
            if onode.isEmpty():
                self.__removeNode(onode)
                del self.ntable[oval]
        else:
            self.ctable[oval] -= 1
            self.ntable[oval].removeKey(key)
            if self.ctable[oval] == 0:
                del self.ctable[oval]
            if nval not in self.ctable:
                self.ctable[nval] = 1
            else:
                self.ctable[nval] += 1
            if nval not in self.ntable:
                self.ntable[nval] = ListNode()
                self.ntable[nval].addKey(key)
                self.__insertAfter(onode, self.ntable[nval])
            else:
                self.ntable[nval].addKey(key)
            if onode.isEmpty():
                self.__removeNode(onode)
                del self.ntable[oval]

    def getMaxKey(self) -> str:
        """
        Returns one of the keys with maximal value.
        """
        return self.head.next.getKey()

    def getMinKey(self) -> str:
        """
        Returns one of the keys with Minimal value.
        """
        return self.tail.pre.getKey()
